This invention relates to fast Fourier transform (FFT) processors, and particularly to those processors used for pipeline FFT operations for real-time or quasi-real time operation.
Many signal transmissions occur in environments in which they are corrupted by broad-band noise, which tends to obscure the signal. The Fourier transform of signal corrupted by noise often improves the detectability of the signal in the presence of such noise. In general, the Fourier transform of a time-varying signal used for communication or detection results in significant signal-related amplitude concentrated within a comparatively narrow frequency range. Specific applications of Fourier transforms include ranging and detection systems such as radar and sonar.
The fast Fourier transform (FFT) is a method which can be used with certain processors for reducing the time or computational effort involved in finding a discrete Fourier transform (DFT) in a digital processing system, as described in the article "A Guided Tour of the Fast Fourier Transform," by Bergland published at pp. 41-51 in the July 1969 issue of IEEE Spectrum. For systems such as radar and sonar which are used for guidance of ships and aircraft, it is important that the location display of targets be performed substantially real-time. In this context, real-time means that the display should correspond substantially to the current position of the targets, where currency is related to the speed of motion of the target or the vehicle in which the display is monitored. Thus, a delay of one second in the display of a ship might be tolerable, where the display is used solely for navigation, whereas for detection or guidance of missiles, much shorter processing times would be necessary.
Short processing times are often associated with processing by the pipeline technique, as opposed to batch processing. In the pipeline technique, sensor data continuously or almost continuously flows through a processor to produce a continuous stream of processed results, delayed only by the processor delay. A pipelined FFT processor is described in U.S. Pat. No. 3,816,729 issued June 11, 1974 in the name of Works. The Works pipeline processor implements the Cooley-Tukey FFT algorithm by cascading a plurality of units, each including a plurality of processors, each processor of which includes a multiplier and two summers, together with switching and delay circuits. The pipeline processor further includes a rotation vector memory and control logic for controlling the operations of the various cascaded units and processors. The Works system is disadvantageous because at each step of the butterfly processing a separate processor is required for each node, as for example FIG. 1 of Works illustrates a 3-stage system to produce an 8-point FFT, where the number of points may be calculated as 2.sup.3 =8. The Works system requires one processor for each of the three steps, for a total of three processors. The amount of memory associated with each processor grows geometrically at each step of the processing, as illustrated for example in FIGS. 1 and 2 the article "Implementation Of A Pipeline FFT", by Sheats and Vickers, published NEREM 70, and in the article "A Pipeline Fast Fourier Transform" by Groginsky & Works, published Eascom 1969, so the amount of memory required may become large when several steps of processing are involved.
An improved FFT processor is desired, in which the memory requirements for the processors are equalized.